﻿// 4205. 树的增边.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4208/

二分图又称作二部图，是图论中的一种特殊模型。
设 G=(V,E)
 是一个无向图，如果顶点 V
 可分割为两个互不相交的子集 (A,B)
，并且图中的每条边 (i,j)
 所关联的两个顶点 i
 和 j
 分别属于这两个不同的顶点集 (i∈A,j∈B)
，则称图 G
 为一个二分图。
所有的树都是二分图。

给定一个 n
 个节点的树。

树的节点编号为 1∼n
。

请你为这棵树增加一些边，要求增边后的图形仍是二分图，并且不含重边和自环。

请问，最多可以增加多少条边。

输入格式
第一行包含整数 n
，表示树的节点数量。

接下来 n−1
 行，每行包含两个整数 a,b
，表示节点 a
 和节点 b
 之间存在一条边。

输出格式
一个整数，表示可以增加的边的最大数量。

数据范围
前三个测试点满足 1≤n≤10
。
所有测试点满足 1≤n≤105
，1≤a,b≤n
。

输入样例1：
3
1 2
1 3
输出样例1：
0
输入样例2：
5
1 2
2 3
3 4
4 5
输出样例2：
2
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 